package cn.edu.jxau.test;

public class Main {

	public static void main(String[] args) {

		ListNode a = new ListNode(1);
		a.append(2).append(3);
		ListNode b = new ListNode(1);
		b.append(2);
		ListNode cur = plusAB(a, null);
		while (cur != null) {
			System.out.print(cur.val + " ");
			cur = cur.next;
		}
	}

	public static ListNode plusAB(ListNode a, ListNode b) {

		// 1.填充0节点 //
		int lenA = length(a);
		int lenB = length(b);
		int paddingLen = lenA - lenB;
		if (paddingLen != 0) {
			if (paddingLen < 0) { // 链表a需填充paddingLen个0结点
				paddingLen = -paddingLen;
				for (int i = 0; i < paddingLen; i++) {
					ListNode n = new ListNode(0);
					n.next = a;
					a = n;
				}
			} else { // 链表b需填充paddingLen个0结点
				for (int i = 0; i < paddingLen; i++) {
					ListNode n = new ListNode(0);
					n.next = b;
					b = n;
				}
			}
		}
		// 2.add //
		Sum sum = plusAB0(a, b);
		// 3.处理进位 //
		if (sum.carry != 0) {
			ListNode result = new ListNode(sum.carry);
			result.next = sum.sum;
			return result;
		} else {
			return sum.sum;
		}
	}

	private static Sum plusAB0(ListNode a, ListNode b) {

		if (a == null && b == null) {
			return new Sum();
		}
		Sum sum = plusAB0(a.next, b.next);
		int val = sum.carry + a.val + b.val;
		ListNode node = new ListNode(val % 10);
		node.next = sum.sum;
		sum.sum = node;
		sum.carry = val / 10;
		return sum;
	}

	private static int length(ListNode a) {

		ListNode cur = a;
		int count = 0;
		while (cur != null) {
			count++;
			cur = cur.next;
		}
		return count;
	}
}

class Sum {
	public ListNode sum;
	public int carry;

	public Sum() {

	}
}

class ListNode {
	public int val;
	public ListNode next;

	ListNode(int val) {
		this.val = val;
	}

	public ListNode append(int val) {

		ListNode node = new ListNode(val);
		node.next = this.next;
		this.next = node;
		return node;
	}
}
